package formal.tree.recursion;

import java.util.HashMap;

/**
 * 打家劫舍 III
 *
 * @author DengYuan2
 * @create 2021-01-18 21:28
 */
public class M_337 {
    public static void main(String[] args) {
        Integer[] a = {3, 2, 3, null, 3, null, 1};
        TreeNode treeNode = TreeNode.generateTree(a);
        int res = rob2(treeNode);
        System.out.println(res);

    }

    /**
     * 不会-大神的写法-思路优秀啊！！
     * 思路：https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/
     *
     * @param root
     * @return
     */
    public static int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int val1 = root.val;
        if (root.left != null) {
            val1 += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            val1 += rob(root.right.left) + rob(root.right.right);
        }
        int val2 = rob(root.left) + rob(root.right);
        return Math.max(val1, val2);
    }

    public static int rob2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        HashMap<TreeNode, Integer> map = new HashMap<>(16);
        robHelper(root,map);
        return map.get(root);
    }


    public static int robHelper(TreeNode root, HashMap<TreeNode, Integer> map) {
        if (root==null){
            return 0;
        }
        if (map.get(root)!=null){
            return map.get(root);
        }
        int val1=root.val;
        if (root.left!=null){
            val1+=robHelper(root.left.left,map)+robHelper(root.left.right,map);
        }
        if (root.right!=null){
            val1+=robHelper(root.right.left,map)+robHelper(root.right.right,map);
        }
        int val2 = robHelper(root.left,map)+robHelper(root.right,map);
        map.put(root,Math.max(val1,val2));
        return Math.max(val1,val2);
    }

    //todo 更简单快速的方法没有继续看
}
